# 01背包问题 (0/1 Knapsack Problem)
# Date: 2025/3/22

"""
背包问题（Knapsack Problem）是一类经典的组合优化问题，主要研究在给定的资源（物品）约束下，如何选择最优方案以最大化（或最小化）某个目标。
其核心思想是：给定一定容量的背包，如何从一组物品中选择若干个，使得总价值最大，同时总重量不超过背包容量。

一. 01背包
在 01背包问题 中，每个物品只能选或不选，不能拆分成部分放入。
给定 n 件物品，每件物品有：价值 v[i] 和 重量 w[i]
给定一个容量为 W 的背包，求如何选择物品使得总价值最大，且总重量不超过 W。

回溯法解法
  由于每个物品只有两种状态: 取或者不取, 所以暴力解法的时间复杂度为O(n^2)

动态规划解法
  设 dp[i][j] 表示在前 i 个物品中选取，且当前背包容量为 j 时，可获得的最大价值：
  dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

  - 不选第 i 个物品：价值等于前 i-1 个物品的最优解，即 dp[i-1][j] 。
  - 选第 i 个物品：价值为前 i-1 个物品的最优解 + 当前物品价值 v[i] ，但前提是容量足够，即 j >= w[i] 。

  时间复杂度: O(nW) （二维 DP）
  空间优化：使用一维数组优化到 O(W)

二. 完全背包
区别于01背包, 在 完全背包问题 中，每个物品可以被选无限次。
动态规划转移方程:
    dp[j]=max(dp[j], dp[j−w[i]]+v[i])
    这里不同于 0-1 背包，我们不从 i−1 维度转移，而是从当前 i 本身转移，因为物品可以被重复选择。

三. 多重背包
在多重背包问题中, 每个物品可以被选取c[i]次.
"""

"""
题目:
一个背包的容量为W, 物品的重量存储在数组arr中, 求背包能存储的最大重量
与标准的01背包问题不同的是, 本题没有价值数组, 重量代替了价值, 实际上是一个求不超过上限的最大子集和
"""


def max_weight_bf(w: int, weights: list[int]):
    """回溯法 也就是暴力解法
    """

    def backtrack(index, current_weight):
        nonlocal max_w
        if current_weight > w:  # 当前物品的重量大于背包的容量
            return
        if index == len(weights):  # 边界条件: 退出递归
            if current_weight > max_w:
                max_w = current_weight
            return
        # 不选择当前物品
        backtrack(index + 1, current_weight)
        # 选择当前物品
        backtrack(index + 1, current_weight + weights[index])

    max_w = 0
    backtrack(0, 0)
    return max_w


def max_weight_classic(w: int, weights: list[int]):
    """使用经典的01背包来求解:
    dp[i][j] 来表示前 i 个物品在容量为 j 的背包中能装的最大重量。
    dp[i][j] = max(dp[i-1][j], dp[i-1][j - weights[i-1]] + weights[i-1])
    """
    n = len(weights)
    # 初始化 dp 数组
    dp = [[0] * (w + 1) for _ in range(n + 1)]

    # 填充 dp 数组
    for i in range(1, n + 1):
        wi = weights[i - 1]  # 第i个物品的重量
        for j in range(1, w + 1):
            if weights[i - 1] > j:  # 如果背包重量为j的情况下不能放下物品i, 则dp[i][j]直接置为dp[i-1][j]
                dp[i][j] = dp[i - 1][j]
            else:  # 如果能放下物品i, 则dp[i][j]为不放物品i时和放入物品i时的较大的一个的重量
                # dp[i - 1][j - weights[i - 1]]表示在留出物品i的重量时的背包最大重量
                # j - weights[i - 1] 表示在最大容量为j的背包中, 留出物品i的重量后的最大重量
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wi] + wi)

    return dp[n][w]


def max_weight_opt(a: int, weights: list[int]):
    """
    由于 dp[i][j] 只依赖于 dp[i-1][j] 和 dp[i-1][j - weights[i-1]]，也就是他们都只依赖于dp[i-1]这一行的数据.
    因此, 我们可以使用一维数组来优化空间复杂度, 这种优化也叫做滚动数组
    我们定义 dp[j] 为背包的最大容量为j时能装的最大重量
    注意: 在01背包中, 由于每个物品只能选择一次, 所以dp[i][j]依赖于dp[i-1][j], 也就是每次更新需要考虑前一次未考虑该物品时候的状态.
    所以在使用滚动数组的时候就需要倒叙更新:
    由于dp[j]需要dp[j-weights[i-1]]的数据, 也就是需要前面的数据, 为了防止dp数组被污染, 所以就需要逆序的遍历
    在求dp[5]时, dp[5] = max(dp[5], dp[5 - 3] + values[3]), 那么就需要dp[2], 如果是正序遍历, 则dp[2]的值也已经经历过计算了
    所以只能使用逆序遍历
    """
    dp = [0] * (a + 1)

    for weight in weights:  # 遍历每一个物品
        for j in range(a, weight - 1, -1):  # 注意: 逆序的遍历每一个背包的最大容量, 在小于当前物品重量的时候停止
            dp[j] = max(dp[j], dp[j - weight] + weight)  # dp[j]表示的是不放

    return dp[a]


if __name__ == '__main__':
    print(max_weight_bf(10, [9, 1, 3, 5, 8]))
    print(max_weight_classic(10, [9, 1, 3, 5, 8]))
    print(max_weight_opt(10, [9, 1, 3, 5, 8]))
